package com.dragon.queue;

/**
 * 用数组实现的循环队列
 *
 * @author dragon
 * @since 2019/11/19
 */
public class LoopQueue2 {

    /**
     * 真正存储元素的数组
     */
    private int[] elementData;

    /**
     * 保存队列中队首的索引
     */
    private int head;

    /**
     * 保存下一个要插入到队列中的索引
     */
    private int tail;

    /**
     * 默认的队列的容量
     */
    private static final int DEFAULT_CAPACITY = 5;

    public LoopQueue2() {
        elementData = new int[DEFAULT_CAPACITY];
        head = tail = 0;
    }

    /**
     * 我们预定初始化的时候，head = tail = 0; 当出队列，元素个数为0的时候，head = tail 了， 这个时候队列也是空的队列
     */
    public boolean isEmpty() {
        return head == tail;
    }

    /**
     * 我们预留了一个空间，如果不预留的话，head就等于tail，这个时候没有办法判断出队列是否为空了，所以预留了一个空间
     * 0  1  2  3  4  5
     * -- -- -- -- -- --
     * 1  2  3  5  6  7
     * t  h
     * 索引1：是最后一个元素
     * 索引2: 是代表tail，也就是下一个元素将要被添加到队列中的索引位置
     * 索引3：是代表的head,也就是队列的队首元素
     * <p>
     * 角标2号位不能被插入元素，因为如果插入了元素，则head = tail， 也就是说不能判断队列是否为空了
     * <p>
     * 所以我们预留一个元素空间的位置，这样我们能够通过(tail + 1) % elementData.length == head ,则代表队列已满
     */
    public boolean isFull() {

        return ((tail + 1) % elementData.length) == head;
    }

    /**
     * 获得队列中的元素个数
     *
     * @return
     */
    public int size() {
        return (tail - head + elementData.length) % elementData.length;
    }

    /**
     * 入队
     *
     * @param num
     */
    public void enqueue(int num) {
        if (isFull()) {
            throw new RuntimeException("LoopQueue is Full");
        }

        elementData[tail] = num;

        tail = (tail + 1) % elementData.length;
    }

    /**
     * 出队
     *
     * @return
     */
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("LoopQueue is Empty");
        }

        int returnNum = elementData[head];
        elementData[head] = 0;
        head = (head + 1) % elementData.length;

        return returnNum;
    }
}
